import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode pop = null;

        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                TreeNode peek = stack.peek();

                if (peek.right == null || pop == peek.right) {
                    pop = stack.pop();
                    list.add(pop.val);
                } else {
                    root = peek.right;
                }
            }
        }

        return list;
    }
}

public class PostorderTraversal_Iteration {
    public static void main(String[] args) {
        // 构建测试用的二叉树 [1,null,2,3]
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);

        // 执行后序遍历
        Solution solution = new Solution();
        List<Integer> result = solution.postorderTraversal(root);

        // 输出结果
        System.out.println("后序遍历结果：" + result);
        // 预期输出：[3, 2, 1]
    }
}    